import java.util.*;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        // 遍历所给的字符串数组
        for(String x : strs) {
            // 给这个 x 排序
            char[] ch = x.toCharArray();
            Arrays.sort(ch);
            // 用新的 String 引用变量 key 保存这个排序后的字符串
            String key = new String(ch);

            if(!map.containsKey(key)) {
                // 如果Map中还没有这个字符串, 就创建一个新的键值对来存放
                map.put(key, new ArrayList<>());
            }
            // 如果多个字符串是异位词, 那么排序后的 key 都是相同的
            // 则从 map 中找到对应的存放异位词的数组, 把源字符串 add进去
            map.get(key).add(x);
        }

        return new ArrayList<>(map.values());
    }
}
